Data compression is an important computer operation used in many computing applications, including both server and client applications. For example, data compression may be used to reduce network bandwidth requirements and/or storage requirements for cloud computing applications.
Many common lossless compression formats are based on the LZ77 compression algorithm. Data compressed using LZ77-based algorithms typically include a stream of symbols (or “tokens”). Each symbol may include literal data that is to be copied to the output or a reference to repeat data that has already been decompressed. The DEFLATE algorithm uses LZ77 compression in combination with Huffman encoding to generate compressed output. The DEFLATE algorithm supports dynamic Huffman codes as well as static Huffman codes. Typical encoders may analyze a message block and generate an optimum Huffman code in a first pass through the message block, and then perform substitution of the symbols into variable length prefix codes in a second pass through the message block.